package top.lcm668.study.oj.base.sortmethods;

/**
 * @author: Coder-Lcm
 * @date: 2021/10/5 14:37
 * 快速排序
 */
public class QuickSort<T extends Comparable<T>> extends BaseSort<T> {
    @Override
    protected void sort(T[] arr, boolean isAsc) {
        quickSort(arr, 0, arr.length - 1, isAsc);
    }

    protected void quickSort(T[] arr, int start, int end, boolean isAsc) {
        int len = arr.length;
        if (len <= 1 || start < 0 || end >= len || start > end) {
            return;
        }
        int smallIndex = partition(arr, start, end, isAsc);
        if (smallIndex > start) {
            quickSort(arr, start, smallIndex - 1, isAsc);
        }
        if (smallIndex < end) {
            quickSort(arr, smallIndex + 1, end, isAsc);
        }
    }

    /**
     * 切分
     * @param nums
     * @param start
     * @param end
     * @return
     */
    private int partition(T[] nums, int start, int end, boolean isAsc) {
        int pivot = (int) (start + Math.random() * (end - start + 1));
        int smallIndex = start - 1;
        swap(nums, pivot, end);
        for (int i = start; i <= end; i++) {
            if (isAsc ? lessThanOrEquals(nums[i], nums[end]) : largeThanOrEquals(nums[i], nums[end])) {
                smallIndex++;
                if (i > smallIndex) {
                    swap(nums, i, smallIndex);
                }
            }
        }
        return smallIndex;
    }
}
